1. Field of the Invention
The present invention relates to an error correction in encoding of convolutional codes and a decoding of convolutional codes using a Viterbi decoder for correcting errors in a digital data communication system.
2. Description of the Background Art
In recent years, in a communication system for transmitting speech signals such as an automobile telephone or a portable telephone, the direction of the progress has been pointed toward the realization of a low bit rate implementation in which the speech signals are compressed by using high efficiency encoding, in order to increase the number of channels in the available bandwidth.
In such a low bit rate implementation, the error sensitivity of each bit of the speech signal becomes greater, so that there is a need for protecting the speech signal from communication path error by using error correction codes. Here, the error sensitivity indicates an extent to which the quality of the reproduced signal is deteriorated by the error of each bit, which is different for each bit in the speech signal. In order to utilize the frequency bandwidth efficiently, it is preferable to set the error correction power of the error correction codes according to the error sensitivity of each bit.
To this end, in the conventional error correction method, the speech signals are classified into a plurality of classes according to their error sensitivities, and then encoded by using the error correction codes with different encoding rates for different classes.
A conventional apparatus for realizing such a conventional error correction encoding has a configuration as shown in FIG. 1, in which the speech signals 7 entered from an input terminal 1 are supplied to a speech encoder 2. The speech encoder 2 compresses the speech signals 7, classifies them into a bit sequence 8 having a high error sensitivity for which the deterioration of the speech quality due to the error is large, and a bit sequence 9 having a low error sensitivity for which the deterioration of the speech quality due to the error is small, and supplies these bit sequences 8 and 9 to error correction code encoders 3 and 4, respectively, which are provided in correspondence to these two classes.
The error correction code encoder 3 encodes the bit sequence 8 having a high error sensitivity by using error correction codes having a first encoding rate r.sub.1, while the error correction code encoder 4 encodes the bit sequence 9 having a low error sensitivity by using error correction codes having a second encoding rate r.sub.2 which is larger than the first encoding rate r.sub.1. In general, the error correction power can be made higher for the smaller encoding rate.
Encoded signal sequences 10 and 11 outputted from the error correction code encoders 3 and 4, respectively, are combined into a single signal sequence 12 at a switch 5, and outputted to an output terminal 6.
In this conventional apparatus, the bit sequence 8 having a high error sensitivity can be protected better than the bit sequence 9 having a low error sensitivity because the encoding rate r.sub.1 used for the bit sequence 8 is set to be smaller than the encoding rate r.sub.2 used for the bit sequence 9. The frequency bandwidth can be utilized more efficiently by distributing the redundancy unevenly in such a manner.
For the error correction codes for the speech signals, the convolutional codes have been used because it is possible to realize the very powerful error correction function by carrying out the maximum likelihood decoding such as Viterbi decoding. For example, in the error correction method adopted for the digital cellular system in the United States, the convolutional codes having the encoding rate equal to 1/2 are used for a plurality of bits (called the class 1 bits) having a high error sensitivity among the compressed digital speech signals. In this method, the error correction codes are not used for the bits having a low error sensitivity. In this method, if the digital speech signals are to be encoded at the lower bit rate, the absolute value of the error sensitivity of each bit will become higher, so that there is going to be a need for providing some kind of error correction codes even for the bits having a relatively lower error sensitivity among the encoded speech signals.
Now, for the speech signals in which the data to be encoded are inputted into the convolutional encoder in units of blocks, it is preferable to have a trellis of the convolutional codes terminating for each block. To this end, in order to realize the trellis whose start and end are merging into a particular state, there is a need to start the encoding in a state in which all the shift registers of the encoder are cleared, and to carry out the encoding by attaching m bits of all zero tail bits behind the data bits, where m is the memory length of the encoder, i.e., a number of shift registers in the encoder. The encoding is finished when all of the tail bits are entered into the encoder. Here, when the encoding rate of the convolutional codes is r and a number of data bits is K, the data after the encoding have a length equal to (K+m)/r bits, and the effective encoding rate becomes r.times.K/(K+m) which is smaller than r.
For example, when r=1/2, K=50, and m=6, the data after the encoding have the length equal to 112 bits, so that the effective encoding rate becomes 50/112 which is smaller than the encoding rate 1/2 of the convolutional codes. As such, the effective encoding rate becomes smaller than the encoding rate of the error correction codes in a case of the convolutional encoding of the data block, especially when the block length K is short. As a result, in such a case, the redundancy becomes larger and the frequency bandwidth utilization efficiency becomes lower.
Because of such a property of the convolutional codes, when the convolutional codes are used as the error correction codes in the conventional apparatus such as that shown in FIG. 1, there arises the problem that the redundancy required for terminating the trellis becomes large as the convolutional encoding is going to be applied to two of the data blocks having small block lengths independently. As a consequence, in a system for which the available frequency bandwidth is limited, in order to compensate this large redundancy, either the encoding rate of the convolutional codes must be increased or the number of bits in the speech signal must be made smaller, but the quality of the decoded speech signal is deteriorated in either case.
Moreover, when the classification of the speech signals according to the error sensitivity is made, the block length becomes shorter and the number of blocks becomes greater, so that the redundancy becomes even larger, and the frequency bandwidth utilization efficiency becomes even lower.
Thus, in order to utilize the frequency bandwidth efficiently, it is preferable to carry out the error correction encoding of the digital speech signals by classifying the speech signals according to the error sensitivity of each bit and then encoding these classes separately by using the error correction codes having different encoding rates. However, when the convolutional codes are used for the error correction codes, the redundancy required for terminating the trellis must be provided for each encoder, so that the frequency bandwidth utilization efficiency is rather lowered. Moreover, in the system for which the available frequency bandwidth is limited, there is a need to lower the encoding rate of the convolutional codes or to make the number of bits in the speech signals smaller in order to compensate this redundancy, so that the quality of the decoded speech signal is deteriorated.
Now, the convolutional codes and the Viterbi decoding will be described in further detail.
The convolutional code is a type of an error correction code which is widely used in a communication system such as a satellite broadcasting system and a mobile communication system, because a high encoding gain is achievable by using the convolutional codes in conjunction with the Viterbi decoding.
The Viterbi decoding is a decoding of data encoded by the convolutional encoding or the block encoding, which enable the efficient soft decision decoding.
The convolutional encoder usually includes m shift registers (m is an integer) in which case it is said to have a memory length equal to m. In this convolutional encoder, the stored contents of these shift registers at each state are collectively referred to as a state, and the state of the next stage and two bit output C.sub.i,0 and C.sub.i,1 are determined according to the state of the present stage and 1 bit input data I.sub.i (i=0, 1, 2, . . . ).
A conventional convolutional encoder for carrying out the convolutional encoding with the encoding rate r=1/2 by using two shift registers has a configuration as shown in FIG. 2. In this configuration of FIG. 2, a shift register 22 memorizes the input data for the immediately previous stage, while a shift register 23 memorizes the input data for the two times previous stage. Thus, when the input data I(t) is entered from an input terminal 21, the shift register 22 stores the data I(t-1) and the shift register 23 stores the data I(t-2).
An exclusive OR circuit (referred hereafter as an adder) 24 obtains an exclusive OR of the input data I(t) and the output data I(t-2) of the shift register 23, while an adder 25 obtains the exclusive OR of the input data I(t), the output data I(t-1) of the shift register 22, and the output data I(t-2) of the shift register 23.
The output of the adder 24 is outputted from an output terminal 26 as an encoded data C.sub.0 (t), while the output of the adder 25 is outputted from an output terminal 27 as an encoded data C.sub.1 (t).
Thus, the encoded data C.sub.0 (t) and C.sub.1 (t) can be expressed as follows. EQU C.sub.0 (t)=I(t)+I(t-2) (mod 2) (1) EQU C.sub.1 (t)=I(t)+I(t-1)+I(t-2) (mod 2) (2)
The shift registers 22 and 23 can take one of the following four states S.sub.0 to S.sub.3 according to their stored contents. EQU State S.sub.0 : I(t-1)=0, I(t-2)=0 EQU State S.sub.1 : I(t-1)=0, I(t-2)=1 EQU State S.sub.2 : I(t-1)=1, I(t-2)=0 EQU State S.sub.3 : I(t-1)=1, I(t-2)=1
The encoded data C.sub.0 and C.sub.1 is uniquely determined by the present state and the data I to be entered next, and at the same time the next state to make a transition from the present state is also determined.
All the possible state transitions are summarized in a state transition diagram shown in FIG. 3, where each transition is indicated by an arrow between two states accompanying by the input data I and the output data C.sub.0 and C.sub.1 which caused that transition, in a format of (I/C.sub.0,C.sub.1). For example, when the state at the present stage is S.sub.0 and the input data I.sub.i =1 is entered, the transition to the state S.sub.2 is made, and the output data (C.sub.i,0, C.sub.i,1)=(1, 1) are outputted.
These state transitions can also be represented in a form of the trellis diagram shown in FIG. 4, where each one of lines 101 to 108 joining two states is called a branch, and a series of state transitions joined by the branches is called a path. As in the state transition diagram of FIG. 3, each branch is accompanying by the input data I and the output data C.sub.0 and C.sub.1 which caused that transition, in a format of (I/C.sub.0,C.sub.1).
The Viterbi decoder estimates the data series with the maximum likelihood (data series having the maximum correlation with the received signals) at a high probability by selecting one survivor path which is most likely one among a plurality of paths by which the transition to each state can be realized, for every state that can be realizable in the encoder, at each decoding timing, and outputting a bit located at a position reached by tracing the selected survivor path back for a predetermined length. For the convolutional encoding with the encoding rate equal to 1/n, when the number of shift registers in the encoder is m, the constraint length .nu. is equal to m+1, and the number of states is equal to 2.sup.m.
The conventional Viterbi decoder has a configuration as shown in FIG. 5. In this conventional Viterbi decoder of FIG. 5, a pair of received signals r.sub.0 and r.sub.1, corresponding to the output data C.sub.0 and C.sub.1 of the convolutional encoder, for which a soft decision or a hard decision has been made at each stage, are received at an input terminal 31. These received signals r.sub.0 and r.sub.1 are then supplied to a branch metric calculation circuit 32, which calculates a value called a branch metric indicating the likelihood of each branch in the trellis diagram of FIG. 4 (the correlation of each branch with the received signals), for each of the branches 101 to 108. This branch metric is usually given in a form of a real number in a range of -1 to 1. Here, the higher encoding gain can be achieved by using the soft decision for the received signals r.sub.0 and r.sub.1.
The branch metrics calculated by the branch metric calculation circuit 32 are then supplied to an ACS (Add-Compare-Select) circuit 33. The ACS circuit 33 calculates a value called a path metric which is given by a cumulative total of the branch metrics in each path, and selects the maximum likelihood path among the paths by which the transition to each state can be made, for each of the states S.sub.0 to S.sub.3. For example, in order to select the maximum likelihood path by which the transition to the state S.sub.0 can be made at the (t-1)-th stage in the trellis diagram shown in FIG. 4, the ACS circuit 33 compares a value obtained by adding the path metric of the state S.sub.0 at the (t-2)-th stage and the branch metric of the branch 101 with a value obtained by adding the path metric of the state S.sub.1 at the (t-2)-th stage and the branch metric of the branch 103, and selects the path corresponding to the larger (or smaller) one of these values.
The 2.sup.m path metrics for all of the survivor paths at the previous stage used in this calculation of the path metric at the ACS circuit 33 are stored in a path metric memory 34 and read out to the ACS circuit 33, and the path metrics stored in the path metric memory 34 are updated whenever new path metrics are obtained at the ACS circuit 33.
Also, all the survivor paths at the previous stage are stored in a path memory 35, and in a case of the example described above, the survivor paths for the states S.sub.0 and S.sub.1 at the (t-2)-th stage are read out to the ACS circuit 33, in order to make the selection of the maximum likelihood path.
The ACS circuit 33 outputs an oldest bit in each selected survivor path to an output signal generation circuit 36, while writing the remaining bits of each selected survivor path along with one bit determined by the transition into the path memory 35, so as to update the survivor paths stored in the path memory 35. Here, the one bit to be added to the remaining bits of the survivor path indicates from which one of the two states the transition has been made. For example, in a case of the example described above, when the survivor path for the state S.sub.0 at the (t-1)-th stage is obtained by the transition from the state S.sub.0 at the (t-2)-th stage, the one bit to be added will be "0", whereas when the survivor path for the state S.sub.0 at the (t-1)-th stage is obtained by the transition from the state S.sub.1 at the (t-2)-th stage, the one bit to be added will be "1".
The output signal generation circuit 36 determines one bit output signal from 2.sup.m of the oldest bits of the selected survivor paths. The obtained one bit output signal is then outputted to an output terminal 37 as the decoded signal.
Now, all the survivor paths are going to merge into one path when the trellis diagram is traced backwards for sufficient length. The merged path is theoretically guaranteed to be the maximum likelihood path, but in practice, in order to keep the circuit size and the delay time to practically reasonable values, it is preferable to use a truncation length (a length of the survivor path memorized in the path memory 35) which is as small as possible within a range in which the deterioration of the error rate can be suppressed. Usually, in order for the survivor paths to merge at a high probability, the truncation length is required to have a length which is four to five times as large as the constraint length .nu..
When all the survivor paths are merging, all of 2.sup.m of the oldest bits of the selected survivor paths are equal to the same value, and this value can be taken for the one bit output signal, but in a case all of these 2.sup.m oldest bits are not identical, a determination of the one bit output signal is made by using an appropriate determination procedure such as a selection of the majority among 2.sup.m bits, or a selection of the bit corresponding to the larger path metric.
In such a conventional Viterbi decoder, the decoding error rate can be made smaller for the longer the survivor path, i.e., the longer truncation length, such that the data reliability can be improved. However, the decoding delay time of the decoder is given by (truncation length+constraint length-1) so that the longer truncation length also makes the delay time longer.
In other words, the smallness of the decoding error rate and the shortness of the delay time are mutually conflicting so that they cannot be satisfied simultaneously.
Now, the path memory 35 is required to have a capacity to store 2.sup.m words.times.(truncation length) bits, so that for the codes using the memory length m equal to 6 (i.e., the constraint length equal to 7), setting the truncation length to be four times as long as the constraint length (i.e., equal to 28), the path memory 35 is required to have a capacity of 64 words.times.28 bits=1,792 bits.
In order to implement the Viterbi decoder on a single LSI chip, the path memory 35 can be constructed from a RAM or a register. When the register is used for the path memory, it becomes possible to achieve the high speed processing but the circuit size becomes large, so that the RAM is usually used unless the high speed processing is necessary. For example, in a case of constructing the path memory of 64 words.times.28 bits capacity from the internal RAM of the gate array, 10,050 gates are necessary, whereas when the same path memory is constructed from the register (7 gates), 12,544 gates are necessary.
Also, the path metric memory 34 is required to have a capacity to store 2.sup.m words.times.(a number of digits of path metric) bits, so that for the codes using the memory length m equal to 6 (i.e., the constraint length equal to 7), setting the digits of the path metric to be eight, the path metric memory 34 is required to have a capacity of 64 words.times.8 bits=512 bits. As in the case of the path memory 35 described above, the path metric memory 34 must be constructed from a register in a case the high speed processing is necessary, but otherwise it may be constructed from the internal RAM of the LSI. Here, however, because the capacity of the path metric memory 34 is not so large, so that when the RAM is used for the path metric memory 34, the sizes of the address decoder, input buffer, and output buffer are not negligible, and there is even a case in which the circuit size can be reduced by using the register for the path metric memory 34. For example, the RAM of 64 words.times.8 bits requires 4,182 gates, whereas the register of the same capacity requires only 3,584 gates.
Thus, when the path memory 35 is constructed from the RAM having 10,050 gates and the path metric memory 34 is constructed from the register having 3,584 gates, the total of the path memory 35 and the path metric memory 34 requires 13,634 gates, so that a considerable portion of the LSI must be allocated for these memories.
In addition, the number of words in the memory increases exponentially with respect to the memory length m of the encoder, so that the circuit size required for these memories becomes even larger for the codes using the longer memory length.
Thus, in the conventional Viterbi decoder, the error correction power can be made greater by using the longer memory length, but the complexity of the decoder increases exponentially with respect to the memory length. For this reason, it has been considered desirable to make the size of each component circuit in the Viterbi decoder as small as possible. In particular, in order to implement the Viterbi decoder on a single LSI chip, it has been considered desirable to realize the path memory and the path metric memory which arc required to store a large amount of data in a small size.
Now, in a system in which the data are outputted in units of blocks such as packets, the trellis must be terminated for each block. Namely, in such a system, it is preferable to carry out the encoding such that the start and the end of the trellis become a particular state.
One method of encoding in which the trellis can be terminated is to set the start and the end of the trellis to the particular state in advance, as shown in FIG. 6 in which the start and the end of the trellis is set to the state S.sub.0. In this case, the encoding starts from the state in which all the shift registers of the encoder are cleared, and the data are entered into the encoder with the m bits of all zero tail bits attached at the end. When the number of data bits is K and the encoding rate is 1/2, the length of the encoded data is going to be 2(K+m) bits, and the effective encoding rate is going to be K/{2(K+m)}. In particular, when K is large and m is small, the redundancy is going to be greater than twice, and there is a problem that the transmission frequency bandwidth extension rate is going to be increased. In a system having a limited frequency bandwidth extension rate, there arises a need to apply the puncture process to the particular bits in the encoded data, and this in turn deteriorates the error rate of the decoded data.
In order to cope with these problems, there is an encoding method in which the encoding is started at the state in which the first m bits of the data are already inputted into the shift registers of the encoder, and after the remaining (K-m) bits of the data are inputted into the encoder, the first m bits of the data are inputted into the encoder again.
For example, the trellis diagram shown in FIG. 7 indicates the case in which the first two bits of the data are 1 and 0. The initial state in this case is S.sub.1, and the final state is also going to be S.sub.1. In this encoding method, 2K bits of the encoded data are outputted with respect to the input of K bits of the data, so that the encoding rate is going to be exactly 1/2, and there is no need to apply the puncture process even when the frequency bandwidth extension rate is limited to be up to twice.
The Viterbi decoding is actually carried out for a case of FIG. 6 and for a case of FIG. 7 as follows.
In a case of FIG. 6 in which the initial and final states are predetermined to be S.sub.0, the initial and final states are also known in advance on the decoder side, so that there is a need to control the decoding such that the paths starting from the states other than S.sub.0 and the paths ending at the states other than S.sub.0 are not going to be selected as the survivor paths.
On the other hand, in a case of FIG. 7 in which the initial and final states are determined according to the first m bits of the data, the initial and final states are unknown on the decoder side. For this reason, there is a need to start the decoding from a state in which the path metrics of all the states at the 0-th stage are equal to each other, and it is also not possible to forcefully terminate the end of the decoding to the particular state. For these reasons, in a case of FIG. 7, there is a problem that the average error rate of the decoded data is deteriorated because of the uncertainty of the initial and final states.